# @Time      :2024/3/8 15:02
# @Author    :Dun_Hz
# @FileName  :migong_queue.py
# @Software  :PyCharm
from collections import deque

mi_gong = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 1, 0, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 1, 0, 1],
    [1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 1, 1, 0, 1, 0, 1, 0, 1, 1],
    [1, 1, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [
    lambda x, y: (x + 1, y),
    lambda x, y: (x - 1, y),
    lambda x, y: (x, y + 1),
    lambda x, y: (x, y - 1)
]

def print_path(path):
    CurNode = path[-1]
    realpath = []
    while CurNode[2] != -1:
        realpath.append(CurNode[0:2])
        CurNode = path[CurNode[2]]
    realpath.append(CurNode[0:2])
    realpath.reverse()
    for node in realpath:
        print(node)

def migong_path(x1, y1, x2, y2):
    queue = deque()
    # 起点进队列，队列，先进先出
    queue.append((x1, y1, -1))
    path = []       # 定义一个新列表，记录把NextNode领进来的CurNode元素下标
    while len(queue) > 0:
        CurNode = queue.popleft()       #队首出队
        path.append(CurNode)
        if CurNode[0]==x2 and CurNode[1]==y2:
            print('走到终点了，路径如下：')
            print_path(path)
            return True
        for dir in dirs:
            NextNode = dir(CurNode[0], CurNode[1])
            if mi_gong[NextNode[0]][NextNode[1]] == 0:
                queue.append((NextNode[0],NextNode[1],len(path)-1))     #能走的话，记录位置进队
                mi_gong[NextNode[0]][NextNode[1]] = 2   #标记为已经走过
                # 广度优先搜索，多个路都需要走
    else:
        print('Bug')
        return False


migong_path(1,1,3,2)
for i in mi_gong:
    print(i)